package com.sourcetrip.my.abs;

import com.sourcetrip.utils.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @author: ZhouBert
 * @date: 2020/12/28
 * @description: 二叉堆的抽象类
 * 确定二叉树的底层用数组实现。
 */
public abstract class AbstractBinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {

	protected int DEFAULT_CAPACITY = 10;

	protected E[] elements = (E[]) new Object[DEFAULT_CAPACITY];

	//region	constructor

	/**
	 * 比较器
	 *
	 * @param comparator
	 */
	public AbstractBinaryHeap(Comparator<E> comparator) {
		super(comparator);
	}

	public AbstractBinaryHeap() {
	}



	//endregion

	//region	默认实现

	@Override
	public void clear() {
		elements = (E[]) new Object[DEFAULT_CAPACITY];
		size = 0;
	}

	/**
	 * 获取堆顶元素
	 *
	 * @return
	 */
	@Override
	public E get() {
		rangeCheck(0);
		return elements[0];
	}

	//endregion


	//region	private methods

	/**
	 * 扩容机制
	 *
	 * @param size
	 */
	protected void ensureCapacity(int size) {
		if (size > elements.length) {
			int newSize = (elements.length >> 1) + elements.length;
			E[] tempArr = (E[]) new Object[newSize];
			System.arraycopy(elements, 0, tempArr, 0, elements.length);
			elements = tempArr;
		}
	}

	/**
	 * 判断添加的元素是否为空！
	 * @param ele
	 */
	protected void ensureEleNotNull(E ele){
		if (ele==null){
			throw new IllegalArgumentException("添加的元素不能为空！");
		}
	}

	/**
	 * 交换 index1 和 index2 中元素的值
	 * @param index1
	 * @param index2
	 */
	protected void swap(int index1, int index2) {
		E temp = elements[index1];
		elements[index1] = elements[index2];
		elements[index2] = temp;
	}

	//endregion


	//region	BinaryTreeInfo implements

	/**
	 * 找到节点的右节点
	 *
	 * @param node
	 * @return
	 */
	@Override
	public Object right(Object node) {
		int index = ((int) node << 1) + 2;
		return index >= size ? null : index;
	}

	@Override
	public Object root() {
		return 0;
	}

	@Override
	public Object left(Object node) {
		int index = ((int) node << 1) + 1;
		return index >= size ? null : index;
	}

	@Override
	public Object string(Object node) {
		return elements[(int) node];
	}


	//endregion
}
